package com.leetcode.LC_MED;

import java.util.Stack;

public class LC538 {
    //BST的中序遍历就是从小到大,那么反过来就是从大到小,然后累加就好了.
    Stack<TreeNode> stack = new Stack<>();

    public TreeNode convertBST(TreeNode root) {

        midTraversal(root);
        int tmp = 0;
        while (stack != null && stack.size() > 0) {
            System.out.print(stack.peek().val + ",");
            stack.peek().val = stack.peek().val + tmp;
            tmp = stack.pop().val;
        }
        return root;
    }

    private void midTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            midTraversal(root.left);
        }
        stack.push(root);
        if (root.right != null) {
            midTraversal(root.right);
        }
    }

    //https://leetcode-cn.com/problems/convert-bst-to-greater-tree/comments/
    int num = 0;

    public TreeNode convertBST2(TreeNode root) {
        if (root != null) {
            //遍历右子树
            convertBST2(root.right);
            //遍历顶点
            root.val = root.val + num;
            num = root.val;
            //遍历左子树
            convertBST2(root.left);
            return root;
        }
        return null;
    }
}
